{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Total Importance of Roads"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #graph #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #图 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumImportance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #道路的最大总重要性"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;，表示一个国家里的城市数目。城市编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;。</p>\n",
    "\n",
    "<p>给你一个二维整数数组&nbsp;<code>roads</code>&nbsp;，其中&nbsp;<code>roads[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;表示城市&nbsp;<code>a<sub>i</sub></code>&nbsp;和&nbsp;<code>b<sub>i</sub></code>&nbsp;之间有一条&nbsp;<strong>双向</strong>&nbsp;道路。</p>\n",
    "\n",
    "<p>你需要给每个城市安排一个从 <code>1</code>&nbsp;到 <code>n</code>&nbsp;之间的整数值，且每个值只能被使用 <strong>一次</strong>&nbsp;。道路的 <strong>重要性</strong>&nbsp;定义为这条道路连接的两座城市数值 <strong>之和</strong>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回在最优安排下，<strong>所有道路重要性</strong> 之和 <strong>最大</strong>&nbsp;为多少。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/04/07/ex1drawio.png\" style=\"width: 290px; height: 215px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]\n",
    "<b>输出：</b>43\n",
    "<b>解释：</b>上图展示了国家图和每个城市被安排的值 [2,4,5,3,1] 。\n",
    "- 道路 (0,1) 重要性为 2 + 4 = 6 。\n",
    "- 道路 (1,2) 重要性为 4 + 5 = 9 。\n",
    "- 道路 (2,3) 重要性为 5 + 3 = 8 。\n",
    "- 道路 (0,2) 重要性为 2 + 5 = 7 。\n",
    "- 道路 (1,3) 重要性为 4 + 3 = 7 。\n",
    "- 道路 (2,4) 重要性为 5 + 1 = 6 。\n",
    "所有道路重要性之和为 6 + 9 + 8 + 7 + 7 + 6 = 43 。\n",
    "可以证明，重要性之和不可能超过 43 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/04/07/ex2drawio.png\" style=\"width: 281px; height: 151px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 5, roads = [[0,3],[2,4],[1,3]]\n",
    "<b>输出：</b>20\n",
    "<b>解释：</b>上图展示了国家图和每个城市被安排的值 [4,3,2,5,1] 。\n",
    "- 道路 (0,3) 重要性为 4 + 5 = 9 。\n",
    "- 道路 (2,4) 重要性为 2 + 1 = 3 。\n",
    "- 道路 (1,3) 重要性为 3 + 5 = 8 。\n",
    "所有道路重要性之和为 9 + 3 + 8 = 20 。\n",
    "可以证明，重要性之和不可能超过 20 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= roads.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>roads[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "\t<li>没有重复道路。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-total-importance-of-roads](https://leetcode.cn/problems/maximum-total-importance-of-roads/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-total-importance-of-roads](https://leetcode.cn/problems/maximum-total-importance-of-roads/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]', '5\\n[[0,3],[2,4],[1,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        #排序不等式\n",
    "        deg = [0] * n\n",
    "        for x, y in roads:\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "        deg.sort()\n",
    "        # ans = 0\n",
    "        # for i, d in enumerate(deg, 1):\n",
    "        #     ans += i * d\n",
    "        # return ans\n",
    "        return sum(i *d for i, d in enumerate(deg, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        a=[0]*n\n",
    "        for x,y in roads:\n",
    "            a[x]+=1\n",
    "            a[y]+=1\n",
    "        a.sort()\n",
    "        ans=0\n",
    "        for i,x in enumerate(a,1):\n",
    "            ans+=i*x\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        deg = [0] * n\n",
    "        for x, y in roads:\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "        deg.sort()\n",
    "        return sum(d * i for i, d in enumerate(deg, 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        deg = [0] * n\n",
    "        for x, y in roads:\n",
    "            deg[x] += 1\n",
    "            deg[y] += 1\n",
    "        deg.sort()\n",
    "        return sum(d * i for i, d in enumerate(deg, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        l = [0] * n\n",
    "        for r in roads:\n",
    "            i1, i2 = r\n",
    "            l[i1] += 1\n",
    "            l[i2] += 1\n",
    "        \n",
    "        l.sort(reverse=True)\n",
    "        ret = 0\n",
    "        for i in l:\n",
    "            ret += n * i\n",
    "            n -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        indegrees = [0] * n\n",
    "        for a, b in roads:\n",
    "            indegrees[a] += 1\n",
    "            indegrees[b] += 1\n",
    "        indegrees.sort(key=lambda x: -x)\n",
    "        ans = 0\n",
    "        # print(indegrees)\n",
    "        for i in indegrees:\n",
    "            ans += n * i\n",
    "            n -= 1\n",
    "            # print(ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        # 根据度来排序安排数值，然后BFS遍历得到答案\n",
    "        indgree = [0]*n\n",
    "        for x,y in roads:\n",
    "            indgree[x] += 1\n",
    "            indgree[y] += 1\n",
    "        indgree.sort()\n",
    "        print(indgree)\n",
    "        ans = 0\n",
    "        for i,d in enumerate(indgree,1):\n",
    "            ans += d*i\n",
    "        return ans\n",
    "        # newdict = dict()\n",
    "        # cnt = n\n",
    "        # for k,v in (sorted(indgree.items(),key=lambda x:-x[1])):\n",
    "        #     newdict[k] = cnt \n",
    "        #     cnt -= 1\n",
    "        # # print(newdict)\n",
    "        # # BFS \n",
    "        # ans  =  0\n",
    "        # for x,y in roads:\n",
    "        #     ans += newdict[x]+newdict[y]\n",
    "        # return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        deg = [0] * n\n",
    "        for r in roads:\n",
    "            deg[r[0]] += 1\n",
    "            deg[r[1]] += 1\n",
    "        return sum(i * v for i, v in enumerate(sorted(deg), 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]):\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in roads:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        g.sort(key=len)\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            ans += len(g[i - 1]) * i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        ls = [0]*n\n",
    "        for a, b in roads:\n",
    "            ls[a] += 1\n",
    "            ls[b] += 1\n",
    "        ls.sort()\n",
    "        return sum([(i+1)*ls[i] for i in range(n)])\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        dic = {k:0 for k in range(n)}\n",
    "        for a, b in roads:\n",
    "            dic[a] += 1\n",
    "            dic[b] += 1\n",
    "        dic = sorted(dic.items(), key=lambda x:x[1])\n",
    "        #print(dic)\n",
    "        ind = [0]*n\n",
    "        for i in range(n):\n",
    "            ind[dic[i][0]] = i+1\n",
    "        #print(ind)\n",
    "\n",
    "        return sum([v*ind[k] for k, v in dic])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        ls = [0]*n\n",
    "        for a, b in roads:\n",
    "            ls[a] += 1\n",
    "            ls[b] += 1\n",
    "        ls.sort()\n",
    "        return sum([(i+1)*ls[i] for i in range(n)])\n",
    "\n",
    "\n",
    "\n",
    "        dic = {k:0 for k in range(n)}\n",
    "        for a, b in roads:\n",
    "            dic[a] += 1\n",
    "            dic[b] += 1\n",
    "        dic = sorted(dic.items(), key=lambda x:x[1])\n",
    "        #print(dic)\n",
    "        ind = [0]*n\n",
    "        for i in range(n):\n",
    "            ind[dic[i][0]] = i+1\n",
    "        #print(ind)\n",
    "\n",
    "        return sum([v*ind[k] for k, v in dic])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        ls = [0]*n\n",
    "        for a, b in roads:\n",
    "            ls[a] += 1\n",
    "            ls[b] += 1\n",
    "        ls.sort()\n",
    "        return sum([(i+1)*ls[i] for i in range(n)])\n",
    "\n",
    "\n",
    "\n",
    "        dic = {k:0 for k in range(n)}\n",
    "        for a, b in roads:\n",
    "            dic[a] += 1\n",
    "            dic[b] += 1\n",
    "        dic = sorted(dic.items(), key=lambda x:x[1])\n",
    "        #print(dic)\n",
    "        ind = [0]*n\n",
    "        for i in range(n):\n",
    "            ind[dic[i][0]] = i+1\n",
    "        #print(ind)\n",
    "\n",
    "        return sum([v*ind[k] for k, v in dic])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef maximumImportance(self, n, roads):\n",
    "\t\tcnt = [0] * n\n",
    "\t\tfor u, v in roads:\n",
    "\t\t\tcnt[u] += 1\n",
    "\t\t\tcnt[v] += 1\n",
    "\t\tcnt.sort()\n",
    "\t\treturn sum([(i + 1) * cnt[i] for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        label = [0 for i in range(n)]\n",
    "        for i in range(len(roads)):\n",
    "            a1,a2=roads[i][0],roads[i][1]\n",
    "            label[a1]+=1\n",
    "            label[a2]+=1\n",
    "        label.sort()\n",
    "        resultt=[(i+1)*label[i] for i in range(n)]\n",
    "        return sum(resultt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        # Create a list to store the degree of each city\n",
    "        degrees = [0] * n\n",
    "        \n",
    "        # Calculate the degree of each city\n",
    "        for road in roads:\n",
    "            degrees[road[0]] += 1\n",
    "            degrees[road[1]] += 1\n",
    "        \n",
    "        # Sort the cities by their degrees in descending order\n",
    "        sorted_cities = sorted(range(n), key=lambda x: degrees[x], reverse=True)\n",
    "        \n",
    "        # Assign the values to the cities in the sorted cities list, starting from the highest value (n) and going down to 1\n",
    "        values = [0] * n\n",
    "        value = n\n",
    "        for city in sorted_cities:\n",
    "            values[city] = value\n",
    "            value -= 1\n",
    "        \n",
    "        # Calculate the total importance of all roads\n",
    "        total_importance = 0\n",
    "        for road in roads:\n",
    "            total_importance += values[road[0]] + values[road[1]]\n",
    "        \n",
    "        return total_importance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        degree = [0] * n \n",
    "        for a, b in roads:\n",
    "            degree[a] += 1\n",
    "            degree[b] += 1\n",
    "        index = list(range(n))\n",
    "        index.sort(key=lambda i : -degree[i])\n",
    "        x = n \n",
    "        ans = 0 \n",
    "        for i in index:\n",
    "            ans += degree[i] * x \n",
    "            x -= 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        # Create a list to store the degree of each city\n",
    "        degrees = [0] * n\n",
    "        \n",
    "        # Calculate the degree of each city\n",
    "        for road in roads:\n",
    "            degrees[road[0]] += 1\n",
    "            degrees[road[1]] += 1\n",
    "        \n",
    "        # Sort the cities by their degrees in descending order\n",
    "        sorted_cities = sorted(range(n), key=lambda x: degrees[x], reverse=True)\n",
    "        \n",
    "        # Assign the values to the cities in descending order\n",
    "        values = [0] * n\n",
    "        for i in range(n):\n",
    "            values[sorted_cities[i]] = n - i\n",
    "        \n",
    "        # Calculate the total importance of all roads\n",
    "        total_importance = 0\n",
    "        for road in roads:\n",
    "            total_importance += values[road[0]] + values[road[1]]\n",
    "        \n",
    "        return total_importance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        degrees = [0] * n\n",
    "        for a, b in roads:\n",
    "            degrees[a] += 1\n",
    "            degrees[b] += 1\n",
    "        degrees.sort()\n",
    "        res = sum([i * j for i, j in zip(degrees, list(range(1, n+1)))])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\r\n",
    "        cnt = defaultdict(int)\r\n",
    "        for x, y in roads:\r\n",
    "            cnt[x] -= 1\r\n",
    "            cnt[y] -= 1\r\n",
    "        tmp = list(cnt.values())\r\n",
    "        heapq.heapify(tmp)\r\n",
    "        cur = n\r\n",
    "        res = 0\r\n",
    "        while tmp:\r\n",
    "            now = -heapq.heappop(tmp)\r\n",
    "            #print(now, )\r\n",
    "            res += now * cur\r\n",
    "            cur -= 1\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        deg = [[i, 0] for i in range(n)]\n",
    "        for road in roads:\n",
    "            deg[road[0]][1] += 1\n",
    "            deg[road[1]][1] += 1\n",
    "        deg.sort(key = (lambda x: x[1]))\n",
    "        weight = [0] * n\n",
    "        for i in range(n):\n",
    "            weight[deg[i][0]] = i + 1\n",
    "        ans = 0\n",
    "        for road in roads:\n",
    "            ans += weight[road[0]] + weight[road[1]]\n",
    "        return ans\n",
    "    \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        degree = {i:0 for i in range(n)}\n",
    "        for a, b in roads:\n",
    "            degree[a] += 1\n",
    "            degree[b] += 1\n",
    "        degree = list(degree.items())\n",
    "        degree.sort(key = lambda x:x[1])\n",
    "        weight = {}\n",
    "\n",
    "        for i in range(n):\n",
    "            weight[degree[i][0]] = i + 1\n",
    "\n",
    "        ret = 0\n",
    "        for a, b in roads:\n",
    "            ret += weight[a]\n",
    "            ret += weight[b]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        in_degree = [[i, 0] for i in range(n)]\n",
    "\n",
    "        for a, b in roads:\n",
    "            in_degree[a][-1] += 1\n",
    "            in_degree[b][-1] += 1\n",
    "\n",
    "        in_degree.sort(key = lambda x: x[-1])\n",
    "        \n",
    "        weight = [0] * n\n",
    "        index = 1\n",
    "\n",
    "        for i, _ in in_degree:\n",
    "            weight[i] = index\n",
    "            index += 1\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for i, d in in_degree:\n",
    "            ans += weight[i] * d\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        cnt = [0] * n\n",
    "        for x, y in roads:\n",
    "            cnt[x] += 1\n",
    "            cnt[y] += 1\n",
    "        values = [0] * n\n",
    "        res = [(i, x) for i, x in enumerate(cnt)]\n",
    "        res.sort(key = lambda p:p[1])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            values[res[i][0]] = i + 1\n",
    "        for i in range(n):\n",
    "            ans += cnt[i] * values[i]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        node_degree_lst = [0 for _ in range(n)]\n",
    "        for city1, city2 in roads:\n",
    "            node_degree_lst[city1] += 1\n",
    "            node_degree_lst[city2] += 1\n",
    "        city_important_lst = [(idx, node_degree_lst[idx]) for idx in range(n)]\n",
    "        city_important_lst = sorted(city_important_lst, key=lambda x: x[1], reverse=True)\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            result += (n - i) * city_important_lst[i][1]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        degree = defaultdict(int)\n",
    "        for x, y in roads:\n",
    "            degree[x] += 1\n",
    "            degree[y] += 1\n",
    "        nodes = list(degree.values())\n",
    "        if len(nodes) < n:\n",
    "            nodes += [0] * (n - len(nodes))\n",
    "        nodes.sort()\n",
    "        return sum([x * y for x, y in zip(range(1, n + 1), nodes)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        hs = {}\n",
    "        for i in roads:\n",
    "            for j in i:\n",
    "                if j in hs:\n",
    "                    hs[j]+=1\n",
    "                else:\n",
    "                    hs[j] = 1\n",
    "        ans = {}\n",
    "        for i in sorted(hs.items(), key=lambda y:y[1])[::-1]:\n",
    "            ans[i[0]] = n\n",
    "            n-=1\n",
    "        a = 0\n",
    "        for i in roads:\n",
    "            a += ans[i[0]] + ans[i[1]]\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        cnt = Counter(i for i, j in roads)\n",
    "        cnt += Counter(j for i, j in roads)\n",
    "\n",
    "        cnt = list(cnt.items())\n",
    "        cnt.sort(key=lambda x:x[1],reverse=True)\n",
    "        res = 0\n",
    "        for i, c in enumerate(cnt):\n",
    "            res += (n - i) * c[1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        deg = Counter()\n",
    "        for s,t in roads:\n",
    "            deg[s] += 1\n",
    "            deg[t] += 1\n",
    "        h = []\n",
    "        weight = dict()\n",
    "        for id,d in deg.items(): heappush(h,(-d,id))\n",
    "        for i in range(n,0,-1):\n",
    "            if not h: break\n",
    "            weight[heappop(h)[1]]=i\n",
    "\n",
    "        return sum((weight[s]+weight[t] for s,t in roads))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        num = [[i,0] for i in range(n)]\n",
    "        for i, j in roads:\n",
    "            num[i][1] += 1\n",
    "            num[j][1] += 1\n",
    "        num = sorted(num,key=lambda x:x[:][1])\n",
    "        nums = [0] * n\n",
    "        c = 1\n",
    "        for k in range(n):\n",
    "            nums[num[k][0]] = c\n",
    "            c += 1\n",
    "        count = 0\n",
    "        for i, j in roads:\n",
    "            count = count + nums[i] + nums[j]\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        d=defaultdict(int)\n",
    "        for u,v in roads:\n",
    "            d[u]+=1\n",
    "            d[v]+=1\n",
    "        a = sorted(d.items(), key=lambda x: x[1], reverse=True)\n",
    "        importance=defaultdict(int)\n",
    "        #print(a)\n",
    "        for i,v in enumerate(a):\n",
    "            importance[v[0]]=n-i\n",
    "        #print(importance)\n",
    "        ret=0\n",
    "        for u,v in roads:\n",
    "            ret+=importance[u]+importance[v]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        d = {}\n",
    "        for v in roads:\n",
    "            if not d.get(v[0], None):\n",
    "                d[v[0]] = 0\n",
    "            if not d.get(v[1], None):\n",
    "                d[v[1]] = 0\n",
    "            d[v[0]] += 1\n",
    "            d[v[1]] += 1\n",
    "        d_sort = sorted(d.items(), key=lambda x:x[1], reverse=True)\n",
    "        res = 0\n",
    "        for _, v in d_sort:\n",
    "            res += v * n\n",
    "            n -= 1\n",
    "        return res  \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        d_city = {}\n",
    "        for item in roads:\n",
    "            for city in item:\n",
    "                if city in d_city:\n",
    "                    d_city[city] += 1\n",
    "                else:\n",
    "                    d_city[city] = 1\n",
    "        city_sort = sorted(d_city.items(), key = lambda x: x[1], reverse=True)\n",
    "        city_score = {}\n",
    "        for key, value in city_sort:\n",
    "            city_score[key] = n \n",
    "            n -= 1\n",
    "        sums = 0\n",
    "        for item in roads:\n",
    "            for city in item:\n",
    "                sums += city_score[city]\n",
    "        return sums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        du=[0]*n\n",
    "        for u,v in roads:\n",
    "            du[u]+=1\n",
    "            du[v]+=1\n",
    "        w=[i for i in range(n)]\n",
    "        weight=[]\n",
    "        for  i in range(n):\n",
    "            weight.append([w[i],du[i]])\n",
    "        weight.sort(key=lambda x:x[1])\n",
    "        for i in range(n):\n",
    "            weight[i][1]=i+1\n",
    "        weight.sort(key=lambda x:x[0])\n",
    "        max=0\n",
    "        for u,v in roads:\n",
    "            max+=weight[u][1]+weight[v][1]\n",
    "        return max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        # 简单，稍微统计一下连接的数量就行了\n",
    "        m = {i:0 for i in range(n)}\n",
    "        for u, v in roads:\n",
    "            m[u] += 1\n",
    "            m[v] += 1\n",
    "        \n",
    "        v = sorted(m.values())\n",
    "        return sum(x1*x2 for x1, x2 in zip(v, range(1, n+1)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        degree = [0]*n\n",
    "        for i,j in roads:\n",
    "            degree[i] += 1\n",
    "            degree[j] += 1\n",
    "        score = [[i,j] for i,j in enumerate(degree)]\n",
    "        rank = [0]*n\n",
    "        for i,(idx,_) in enumerate(sorted(score,key=lambda x:x[1]),1):\n",
    "            rank[idx] = i\n",
    "        ans = 0\n",
    "        for x,y in roads:\n",
    "            ans += rank[x] + rank[y]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        nums = []\n",
    "        for s in roads:\n",
    "            nums += s\n",
    "        counts = collections.Counter(nums)\n",
    "        counts = sorted(counts.items(), key= lambda x: x[1], reverse=True)\n",
    "        # print(counts)\n",
    "        answer = 0\n",
    "\n",
    "        i = n\n",
    "        length = len(counts)\n",
    "        while i > 0 and n-i < length:\n",
    "            answer += i * counts[n-i][1]\n",
    "            i -= 1\n",
    "        \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        d = {i: 0 for i in range(n)}\n",
    "        for a, b in roads:\n",
    "            d[a] += 1\n",
    "            d[b] += 1\n",
    "        q = list(d.values())\n",
    "        heapify(q)\n",
    "        return sum(heappop(q) * i for i in range(1, n + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        degree = [0]*n\n",
    "        for i,j in roads:\n",
    "            degree[i] += 1\n",
    "            degree[j] += 1\n",
    "        score = [[i,j] for i,j in enumerate(degree)]\n",
    "        rank = [0]*n\n",
    "        for i,(idx,_) in enumerate(sorted(score,key=lambda x:x[1]),1):\n",
    "            rank[idx] = i\n",
    "        ans = 0\n",
    "        for x,y in roads:\n",
    "            ans += rank[x] + rank[y]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        # 统计所有节点的入度\n",
    "        dic = defaultdict(int)\n",
    "        for f, t in roads:\n",
    "            dic[f] += 1\n",
    "            dic[t] += 1\n",
    "        lst = sorted(dic.values())\n",
    "        ans = 0\n",
    "        for i in range(n, 0, -1):\n",
    "            if lst:\n",
    "                ans += lst.pop() * i\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        # 首先字典adj，用于统计某一结点的边数\n",
    "        adj = collections.defaultdict(int)\n",
    "        for i, j in roads:\n",
    "            adj[i] += 1\n",
    "            adj[j] += 1\n",
    "        lens = [[node, edges_num] for node, edges_num in adj.items()]\n",
    "        # 按节点度逆序排序，后面将度高的节点赋予更高的权重\n",
    "        lens.sort(key=lambda x: -x[1])\n",
    "        weights = collections.defaultdict(int)\n",
    "        # 对所有节点赋权重，这里需要赋权重的节点数可能不等于总节点数，因为某个城市可能是孤立的\n",
    "        for k in range(len(lens)):\n",
    "            weights[lens[k][0]] = n\n",
    "            n -= 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i, j in roads:\n",
    "            ans += weights[i] + weights[j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        c = Counter()\n",
    "        for a, b in roads:\n",
    "            c[a] += 1\n",
    "            c[b] += 1\n",
    "        revByN = sorted((v for k, v in c.items()), reverse=True)\n",
    "        return sum(score*num for score, num in zip(range(n, 0, -1), revByN))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        c = Counter(chain.from_iterable(roads))\n",
    "        ans = 0\n",
    "        for value, (_, road) in zip(range(n, 0, -1), c.most_common()):\n",
    "            ans += value * road\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        cnt = Counter()\n",
    "        for x, y in roads:\n",
    "            cnt[x] += 1\n",
    "            cnt[y] += 1\n",
    "        val = sorted(cnt.values(), reverse=True)\n",
    "        ans = 0\n",
    "        wei = range(n, -1, -1)\n",
    "        for x, y in zip(val, list(range(1, n + 1))[::-1]):\n",
    "            ans += x * y \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        numberdict = defaultdict(int)\n",
    "        lastanwser = 0\n",
    "        anwser = defaultdict(int)\n",
    "        ndict = []\n",
    "        for i in roads:\n",
    "            numberdict[i[0]] += 1\n",
    "            numberdict[i[1]] += 1\n",
    "        for i in numberdict:\n",
    "            ndict.append([i,numberdict[i]])\n",
    "        ndict.sort(key = lambda x :x[1],reverse = True)\n",
    "        lenth = len(ndict)\n",
    "        index = n\n",
    "        for i in ndict:\n",
    "            anwser[i[0]] = index\n",
    "            index -= 1\n",
    "        for i in roads:\n",
    "            lastanwser += (anwser[i[0]] +anwser[i[1]])\n",
    "        return lastanwser"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        d = dict()\n",
    "        for i, j in roads:\n",
    "            if i not in d:\n",
    "                d[i] = []\n",
    "            if j not in d:\n",
    "                d[j] = []\n",
    "            d[i].append(j)\n",
    "            d[j].append(i)\n",
    "        \n",
    "        v = sorted(d.items(), key=lambda x: len(x[1]), reverse=True)\n",
    "        l = [len(i[1]) for i in v]\n",
    "        \n",
    "        sa = list(range(n, 0, -1))\n",
    "        res = 0\n",
    "        for i in range(len(l)):\n",
    "            res += sa[i] * l[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        g = {i :[] for i in range(n)}\n",
    "        \n",
    "        for a, b in roads:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        \n",
    "        t = [(i, len(g[i])) for i in g]\n",
    "        t.sort(key=lambda x:x[1])\n",
    "        \n",
    "        print(t)\n",
    "        for i in range(len(t)):\n",
    "            ans += (i + 1) * t[i][1]\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "#         queue = deque([0])\n",
    "#         visited = set([0])\n",
    "#         while queue:\n",
    "#             cur = queue.popleft()\n",
    "            \n",
    "#             for neighbor in g[cur]:\n",
    "#                 if neighbor in visited:\n",
    "#                     continue\n",
    "                    \n",
    "#                 visited.add(neighbor)\n",
    "#                 ans += (cur + neighbor)\n",
    "#                 print(cur, neighbor)\n",
    "#                 queue.append(neighbor)\n",
    "                \n",
    "#         return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        c = Counter(chain.from_iterable(roads))\n",
    "        ans = 0\n",
    "        for value, (_, road) in zip(range(n, 0, -1), c.most_common()):\n",
    "            ans += value * road\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x, y in roads:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        nodes = sorted(g.keys(), key=lambda x:len(g[x]))\n",
    "        ans = 0\n",
    "        for node in nodes[::-1]:\n",
    "            ans+= len(g[node])*n\n",
    "            n-=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        degreeMap = defaultdict(int)\n",
    "        for a, b in roads:\n",
    "            degreeMap[a] += 1\n",
    "            degreeMap[b] += 1\n",
    "        degree = sorted([v for v in degreeMap.values()], reverse=True)\n",
    "        res = 0\n",
    "        for i, d in enumerate(degree):\n",
    "            res += d * (n - i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        dic = collections.defaultdict(int)\n",
    "        res = [0] * n\n",
    "        # 统计各个城市的 连接数 == 出入度 加和\n",
    "        for x, y in roads:\n",
    "            dic[x] += 1\n",
    "            dic[y] += 1\n",
    "        # 直接依照连接数进行排序 （反转，连接数高的放前面，等下给赋值从n--变化）\n",
    "        tmp = sorted([(road_name, cnt) for road_name, cnt in dic.items()] , key = lambda x: x[1], reverse = True)\n",
    "        # 给各个城市根据排序结果 赋值重要度 从n递减到1\n",
    "        for i, (name, cnt) in enumerate(tmp):\n",
    "            res[name] = n - i \n",
    "        ans = 0\n",
    "        # 遍历加和\n",
    "        for x, y in roads:\n",
    "            ans += res[x] + res[y]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        imp = [0] * n\n",
    "        nb = defaultdict(list)\n",
    "        deg = defaultdict(int)\n",
    "        for a, b in roads:\n",
    "            deg[a] += 1\n",
    "            deg[b] += 1\n",
    "        # print(deg)\n",
    "        tmp = sorted(deg.items(), key=lambda d: -d[1])\n",
    "        # deg.sort(deg.items, key = lambda x : x[0])\n",
    "        # print(tmp)\n",
    "        p = n\n",
    "\n",
    "        for t in tmp:\n",
    "            imp[t[0]] = p\n",
    "            p -= 1\n",
    "        # print(imp)\n",
    "        res = 0\n",
    "        for a, b in roads:\n",
    "            res += (imp[a] + imp[b])\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        counts = dict(zip(range(n), [0 for _ in range(n)]))\n",
    "        for (u, v) in roads:\n",
    "            counts[u] += 1\n",
    "            counts[v] += 1\n",
    "        \n",
    "        degrees = list(sorted(list(counts.values())))\n",
    "        ans = sum(degree * rank for (degree, rank) in  zip(degrees, range(1, n + 1)))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        road_nums = defaultdict(int)\n",
    "        for road in roads:\n",
    "            road_nums[road[0]] += 1\n",
    "            road_nums[road[1]] += 1\n",
    "\n",
    "        importance = [0] * n\n",
    "        value = n\n",
    "        for (k, v) in sorted(road_nums.items(), key = lambda kv: (kv[1], kv[0]), reverse=True):\n",
    "            importance[k] = value\n",
    "            value -= 1\n",
    "            \n",
    "        return sum(importance[road[0]] + importance[road[1]] for road in roads)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for a, b in roads:\n",
    "            d[a].append(b)\n",
    "            d[b].append(a)\n",
    "        cnt = defaultdict(int)\n",
    "        for c in range(n):\n",
    "            cnt[c] = len(d[c])\n",
    "        x = sorted(cnt, key=lambda x:cnt[x])\n",
    "        for i, c in enumerate(x):\n",
    "            cnt[c] = i + 1\n",
    "        ans = 0\n",
    "        for c, v in d.items():\n",
    "            ans += cnt[c] * len(v) + sum(cnt[x] for x in v)\n",
    "        return ans // 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        degress = [0]*n\n",
    "        for a,b in roads:\n",
    "            degress[a] += 1\n",
    "            degress[b] += 1\n",
    "        \n",
    "        degress = [(degress[i], i) for i in range(n)]\n",
    "        degress.sort()\n",
    "        rec = {degress[i][1]:i+1 for i in range(n)}\n",
    "        total = 0\n",
    "        for a,b in roads:\n",
    "            total += (rec[a] + rec[b])\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads) -> int:\n",
    "        lis = [j for i in roads for j in i]\n",
    "        dic = collections.Counter(lis)\n",
    "        dic = sorted(dic.items(),key = lambda x :(-x[-1]))\n",
    "        val = list(range(1,n+1))[::-1]\n",
    "        ans = 0\n",
    "        for ind,v in enumerate(dic):\n",
    "            print(v[-1],val[ind])\n",
    "            ans += v[-1] * val[ind]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]):\n",
    "        cityRoads = [roads[i][j] for j in range(2) for i in range(len(roads))]\n",
    "        c = Counter(cityRoads)\n",
    "        array = []\n",
    "        for idx, nRoads in c.items():\n",
    "            array.append([idx, nRoads])\n",
    "        array.sort(key = lambda x: x[1], reverse = True)\n",
    "        ans = 0\n",
    "        for idx, nRoads in array:\n",
    "            ans += nRoads * n\n",
    "            n -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        import collections\n",
    "        road_connect = collections.defaultdict(list)\n",
    "        res = [0]*n\n",
    "        for road in roads:\n",
    "            road_connect[road[0]].append(road[1])\n",
    "            road_connect[road[1]].append(road[0])\n",
    "        # degrees = {k:len(v) for k,v in road_connect.items()}\n",
    "        sorted_degree = dict(sorted(road_connect.items(), key = lambda x:len(x[1]), reverse = True))\n",
    "        cur_val = n\n",
    "        for key in sorted_degree.keys():\n",
    "            res[key] = cur_val\n",
    "            cur_val-=1\n",
    "        sum_res = 0\n",
    "        for road in roads:\n",
    "            if res[road[0]]==0:\n",
    "                sum_res+=cur_val\n",
    "                cur_val-=1\n",
    "            else:\n",
    "                sum_res+=res[road[0]]\n",
    "            if res[road[1]]==0:\n",
    "                sum_res+=cur_val\n",
    "                cur_val-=1\n",
    "            else:\n",
    "                sum_res+=res[road[1]]\n",
    "        return sum_res\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        sum_r = []\n",
    "        for i in roads:\n",
    "            sum_r+=i\n",
    "        c = Counter(sum_r)\n",
    "        dict(c)\n",
    "        out = sorted(c.items(),key=lambda x:x[1],reverse=True)\n",
    "        sum_r=0\n",
    "        for i,x in enumerate(out):\n",
    "            sum_r+=x[1]*(n-i)\n",
    "        return sum_r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        deg = [0] * n\n",
    "        for a, b in roads:\n",
    "            \n",
    "            deg[a] += 1\n",
    "            deg[b] += 1\n",
    "        arr = [[i, d] for i, d in enumerate(deg)]\n",
    "        arr.sort(key=lambda x: (x[1], x[0]))\n",
    "        map = {}\n",
    "        for i in range(n):\n",
    "            map[arr[i][0]] = i + 1\n",
    "        ans = 0\n",
    "        for a, b in roads:\n",
    "            ans += (map[a] + map[b])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        dic = {k:0 for k in range(n)}\n",
    "        for a, b in roads:\n",
    "            dic[a] += 1\n",
    "            dic[b] += 1\n",
    "        dic = sorted(dic.items(), key=lambda x:x[1])\n",
    "        #print(dic)\n",
    "        ind = [0]*n\n",
    "        for i in range(n):\n",
    "            ind[dic[i][0]] = i+1\n",
    "        #print(ind)\n",
    "\n",
    "        return sum([v*ind[k] for k, v in dic])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        dic = {k:0 for k in range(n)}\n",
    "        for a, b in roads:\n",
    "            dic[a] += 1\n",
    "            dic[b] += 1\n",
    "        dic = sorted(dic.items(), key=lambda x:x[1])\n",
    "        #print(dic)\n",
    "        ind = [0]*n\n",
    "        for i in range(n):\n",
    "            ind[dic[i][0]] = i+1\n",
    "        #print(ind)\n",
    "\n",
    "        return sum([v*ind[k] for k, v in dic])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for n1, n2 in roads:\n",
    "            g[n1].append(n2)\n",
    "            g[n2].append(n1)\n",
    "        outNum = []  # i: 城市 v: 赋值\n",
    "        for i in range(n):\n",
    "            outNum.append([i, len(g[i])])  # (城市，赋值)\n",
    "        # print(outNum)\n",
    "\n",
    "        outNum.sort(key=lambda item: item[1])\n",
    "        for j in range(1, n + 1):\n",
    "            outNum[j - 1][1] = j\n",
    "\n",
    "        resLst = [0] * n\n",
    "        for city, val in outNum:\n",
    "            resLst[city] = val\n",
    "\n",
    "        res = 0\n",
    "        for p1, p2 in roads:\n",
    "            res += resLst[p1] + resLst[p2]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        cnt = [0] * n\n",
    "        for x, y in roads:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "            cnt[x] += 1\n",
    "            cnt[y] += 1\n",
    "        values = [0] * n\n",
    "        res = [(i, x) for i, x in enumerate(cnt)]\n",
    "        res.sort(key = lambda p:p[1])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            values[res[i][0]] = i + 1\n",
    "        for i in range(n):\n",
    "            for j in g[i]:\n",
    "                ans += values[i] + values[j]\n",
    "        return ans // 2\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u, v in roads:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "       \n",
    "        st = sorted(g.items(), key = lambda x:-len(x[1]))\n",
    "        i = n\n",
    "        ans = 0\n",
    "        for k, v in st:\n",
    "            #print(f'k={k},v={v}')\n",
    "            ans += len(v) * i\n",
    "            i -= 1\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        \n",
    "        deg = collections.defaultdict(int)\n",
    "        # deg = [0] * n\n",
    "        graph = collections.defaultdict(list)\n",
    "        for (u, v) in roads:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "            deg[u] += 1\n",
    "            deg[v] += 1\n",
    "        \n",
    "        \n",
    "        deg = sorted(deg.items(), key=lambda x:-x[1])\n",
    "        # score = collections.defaultdict(int)\n",
    "        ans = 0\n",
    "        base = n\n",
    "        for u, d in deg:\n",
    "            ans += d * base\n",
    "            base -= 1\n",
    "        \n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        degree = {i: 0 for i in range(n)}\n",
    "        for i, j in roads:\n",
    "            degree[i] += 1\n",
    "            degree[j] += 1\n",
    "        \n",
    "        a = sorted(range(n), key=lambda x: degree[x])\n",
    "        weight = {v: i + 1 for i, v in enumerate(a)}\n",
    "        res = 0\n",
    "        for i, j in roads:\n",
    "            res += weight[i] + weight[j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        hashTable = {}\n",
    "        for terms in roads:\n",
    "            for i in terms:\n",
    "                if i not in hashTable:\n",
    "                    hashTable[i] = 1\n",
    "                else:\n",
    "                    hashTable[i] += 1\n",
    "        res = []\n",
    "        # print(hashTable)\n",
    "        for i in hashTable:\n",
    "            res.append([i,hashTable[i]])\n",
    "        # print(res)\n",
    "        res = sorted(res,key=lambda x:x[1],reverse=True)\n",
    "        ans = []\n",
    "        print(res)\n",
    "\n",
    "        for terms in res:\n",
    "            ans.append([terms[0],n])\n",
    "            n-=1\n",
    "        # print('ans:',ans)\n",
    "        hashTable2 = {}\n",
    "        for terms in ans:\n",
    "            hashTable2[terms[0]] = terms[1]\n",
    "        out = 0\n",
    "        for terms in roads:\n",
    "            temp = hashTable2[terms[0]]+hashTable2[terms[1]]\n",
    "            # print(temp)\n",
    "            out+=temp\n",
    "        return out\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        # 建图和度\n",
    "        g = collections.defaultdict(list)\n",
    "        degrees = [0]*n\n",
    "        for i, (x, y) in enumerate(roads):\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "            degrees[y] += 1\n",
    "            degrees[x] += 1\n",
    "        print(g, degrees)\n",
    "\n",
    "        values = [-1] * n\n",
    "        sorted_indexes = sorted(range(len(degrees)), key=lambda k: degrees[k])\n",
    "        print(sorted_indexes)\n",
    "        for i, s_idx in enumerate(sorted_indexes):\n",
    "            values[s_idx] = i+1\n",
    "        print(values)\n",
    "\n",
    "        res = 0\n",
    "        for x, y in roads:\n",
    "            res += (values[x] + values[y])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        hashTable = {}\n",
    "        for terms in roads:\n",
    "            for i in terms:\n",
    "                if i not in hashTable:\n",
    "                    hashTable[i] = 1\n",
    "                else:\n",
    "                    hashTable[i] += 1\n",
    "        res = []\n",
    "        print(hashTable)\n",
    "        for i in hashTable:\n",
    "            res.append([i,hashTable[i]])\n",
    "        print(res)\n",
    "        res = sorted(res,key=lambda x:x[1],reverse=True)\n",
    "        ans = []\n",
    "        print(res)\n",
    "\n",
    "        for terms in res:\n",
    "            ans.append([terms[0],n])\n",
    "            n-=1\n",
    "        print('ans:',ans)\n",
    "        hashTable2 = {}\n",
    "        for terms in ans:\n",
    "            hashTable2[terms[0]] = terms[1]\n",
    "        out = 0\n",
    "        for terms in roads:\n",
    "            temp = hashTable2[terms[0]]+hashTable2[terms[1]]\n",
    "            # print(temp)\n",
    "            out+=temp\n",
    "        return out\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        indegree = Counter()\n",
    "        g = collections.defaultdict(list)\n",
    "        for x, y in roads:\n",
    "            indegree[x] += 1\n",
    "            indegree[y] += 1\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        f = [(v, k) for k, v in indegree.items()]\n",
    "        f.sort(reverse = True)\n",
    "        res = 0\n",
    "        for i in range(len(f)):\n",
    "            print(n-i, f[i][0])\n",
    "            res += (n - i) * f[i][0]\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        index_edge = {}\n",
    "        for c1, c2 in roads:\n",
    "            index_edge[c1] = index_edge.get(c1,0)+1\n",
    "            index_edge[c2] = index_edge.get(c2,0)+1\n",
    "        # print(index_edge)\n",
    "\n",
    "        hp_edge_index = []\n",
    "        for index, edge in index_edge.items():\n",
    "            pair = [-edge, index]\n",
    "            heapq.heappush(hp_edge_index, pair)\n",
    "        # print(hp_edge_index)\n",
    "        index_point = {}\n",
    "        while len(hp_edge_index) > 0:\n",
    "            edge, index = heapq.heappop(hp_edge_index)\n",
    "            print(edge, index)\n",
    "            index_point[index] = n\n",
    "            n -= 1\n",
    "        # print(index_point)\n",
    "        cnt = 0\n",
    "        for c1, c2 in roads:\n",
    "            cnt += index_point[c1] + index_point[c2]\n",
    "        return cnt\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "城市本身的数字是被安排上的，这些数字是凑够1到n\n",
    "\n",
    "已知的是城市的数量和城市之间的道路\n",
    "\n",
    "看起来一个城市连接的边越多，这个城市越重要，这个城市安排的数字越大\n",
    "\n",
    "那么我需要一个优先队列，将每个节点按照他们的边的数量进行排序\n",
    "\n",
    "这个优先队列中的元素的样子为[边的数量，城市的index]\n",
    "\n",
    "pop出来之后保存到字典中，每个元素是[城市的index：安排的分数]，按照pop出来的顺序，分数从高到低\n",
    "\n",
    "那么首先需要计算每个index的城市的边的数量\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        dic = collections.defaultdict(list)\n",
    "        for c1, c2 in roads:\n",
    "            dic[c1].append(c2)\n",
    "            dic[c2].append(c1)\n",
    "        \n",
    "        ls = []\n",
    "        for city, tmp in dic.items():\n",
    "            ls.append((city, len(tmp)))\n",
    "        ls.sort(key=lambda x:x[1],reverse=True)\n",
    "        \n",
    "        i, m = 0, len(ls)\n",
    "        imval = dict()\n",
    "        while i < m - 1:\n",
    "            if ls[i][1] != ls[i+1][1]:\n",
    "                imval[ls[i][0]] = n-i\n",
    "            else:\n",
    "                tmp1 = dic[ls[i][0]].sort()\n",
    "                tmp2 = dic[ls[i+1][0]].sort()\n",
    "                if tmp1 == tmp2:\n",
    "                    imval[ls[i][0]] = n-i\n",
    "                else:\n",
    "                    t1, t2 = 0, 0\n",
    "                    for city in tmp1:\n",
    "                        t1 += len(dic[city])\n",
    "                    for city in tmp2:\n",
    "                        t2 += len(dic[city])\n",
    "                    if t1 < t2:\n",
    "                        interval = ls[i]\n",
    "                        ls[i] = ls[i+1]\n",
    "                        ls[i+1] = interval\n",
    "                    imval[ls[i][0]] = n-i\n",
    "            i += 1\n",
    "        imval[ls[-1][0]] = n - i\n",
    "        \n",
    "        res = 0\n",
    "        for c1, c2 in roads:\n",
    "            val = (imval[c1] + imval[c2])\n",
    "            res += val\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:\n",
    "        Counter = {}\n",
    "        for i, j in roads:\n",
    "            Counter[i] = Counter.get(i, 0) + 1\n",
    "            Counter[j] = Counter.get(j, 0) + 1\n",
    "        freq = [[c, i] for i, c in Counter.items()]\n",
    "        freq.sort(reverse=True)\n",
    "        importance = {}\n",
    "        for index, (c, i) in enumerate(freq):\n",
    "            importance[i] = n - index\n",
    "        total = 0\n",
    "        for i, j in roads:\n",
    "            total += importance[i]\n",
    "            total += importance[j]\n",
    "        return total\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
